ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..2

ИСХОДНЫЕ ДАННЫЕ..3

РАСЧЕТНАЯ ЧАСТЬ.4

МЕТОД ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ .8

ЗАКЛЮЧЕНИЕ…9

СПИСОК БИБЛИОГРАФИЧЕСКИХ ИСТОЧНИКОВ.10

ПРИЛОЖЕНИЕ А.11

Внимание!

Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №3648, цена оригинала 1000 рублей. Оформлена в программе Microsoft Word.

Оплата. Контакты.

ВВЕДЕНИЕ

В курсовой работе по дисциплине «Теория игр в управлении интеллектуальными мобильными роботами» представлены решения матричных игр разной размерности с помощью аналитического метода и применения линейного программирования.

ИСХОДНЫЕ ДАННЫЕ

Мобильный робот I (МР-1) атакует n объектов стоимостями b, (i=1, 2,, n),

мобильный робот II (МР-2) охраняет. МР-1 и МР-2 могут атаковать и защищать по одному объекту. i-й неохраняемый объект МР-1 может поразить с вероятностью pi, охраняемый — с вероятностью 1-р.

1) Составить модель игры при n=3 и решить ее.

2) Составить модель игры при n=7 и решить, преобразовав ее в задачу линейного программирования.

Исходные данные:

a) n=3, b1=1, b2=b3=2, p=0.9, pi=0.9;

б) n=7, b1= b2 =3, b3= b4 =2, b5 = b6 = b7 = 3, p=1, pi=0.7.

РАСЧЕТНАЯ ЧАСТЬ

Составить модель игры при n=3

Мобильный робот I (МР-1) атакует 3 объекта, стоимость которых составляет:

b1 = 1;

b2 = b3 = 2;

Мобильный робот II (МР-2) охраняет эти объекты. МР-1 и МР-1 могут атаковать и защищать по одному объекту. Один из неохраняемых объектов МР-1 может поразить с вероятностью 0.9, охраняемый — с вероятностью 1-0.9 = 0,1. На основании этих данных составлена таблица 1.

Из чего получим матрицу игры:

A=((0.1&0.9&0.9@1.8&0.2&1.8@1.8&1.8&0.2))

При выполнении проверки наличия доминируемых строк и столбцов, было обнаружено их отсутствие, следовательно в дальнейшем будет решаться задача размерности 3х3.

Необходимо выполнить проверку на существование в платежной матрице седловой точки. Нижнее и верхние значения матричной игры равны:

¯v=min⁡max a_ij

Минмакс и максмин для игры ГА могут быть найдены по следующей схеме:

нижнее значение (maxmin) ▁v = 0, а верхнее значение (minmax) ¯v=1,8. Данная матричная игра ГА не имеет седловой точки, а также в игре не существует ситуации равновесия, следовательно максимальная и минимальная стратегия не являются оптимальными. —

Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

Необходимо выполнить проверку на существовании в платежной матрице на доминирующих строк и доминирующих столбцы.

В платежной матрице отсутствуют доминирующие строки. В платежной матрице отсутствуют доминирующие столбцы.

Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

Цель игрока 1 получить максимальную выручку от атаки. выручка, представляется общей стоимостью пораженных роботов

Для нахождения оптимальных стратегий игрока I — X^T=(x_1,x_2,x_3 ) и игрока II — y^T=(y_1,y_2,y_3) были составлены системы уравнений:

y_1^*= ((Δ_1 ) ̃ )/Δ ̃ =2.56/5.12=0.17;

y_2^*= -(Δ_2 ) ̃/Δ ̃ =1.28/5.12=0.415;

y_3^*= (Δ_3 ) ̃/Δ ̃ =1.2/5.12=0.415;

Следовательно, оптимальная стратегия МР-2: Y = (0.17; 0.415; 0.415).

МЕТОД ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Пусть мобильный робот I (МР-1) намерен атаковать один из объектов с1…с7, которые имеют положительные стоимости b1= b2 =3, b3= b4 =2, b5 = b6 = b7 = 3. Мобильный робот II (МР-2) охраняет один из этих объектов. МР-1 и МР-1 могут атаковать и защищать по одному объекту. Будем считать, что если атакован незащищенный объект сi, то он с достоверностью pi = 0.7 уничтожается (игрок 1 выигрывает bi*pi), а защищенный — поражается с вероятностью 1-p.

Требуется составить модель игры при n=7, методом линейного программирования. bi=3, p=1, pi=0.8.

Мобильный робот I (МР-1) атакует 7 объекта стоимостями bi=3, мобильный робот II (МР-2) охраняет. МР-1 и МР-1 могут атаковать и защищать по одному объекту. i-й неохраняемый объект МР-1 может поразить с вероятностью 0.1, охраняемый — с вероятностью 1-1=0.

При решении задач большей размерности целесообразно использовании методов линейного программирования. Тогда возникает необходимость представления игровой ситуации в виде, удобном для расчета.

Цель МР-1 получить максимальную выручку от атаки. Выручка, представляется стоимостью пораженного объекта. Некоторые объекты имеют более низкую стоимость, поэтому их атака считается неприоритетной.

Данные задачи для использования метода линейного программирования: n=7, b1= b2 =3, b3= b4 =2, b5 = b6 = b7 = 3, p=1, pi=0.7.

При решении задач большей размерности целесообразно использовании методов линейного программирования. Тогда возникает необходимость представления игровой ситуации в виде, удобном для расчета.

Пусть цена игры V>0. Для этого достаточно, чтобы для каждого элемента платежной матрицы aij выполнялось неравенство aij>0.

Игровая матрица при n=7 выглядит следующим образом:

0 2.8 2.1 2.1 2.8 2.8 2.8

2.8 0 2.1 2.1 2.8 2.8 2.8

2.8 2.8 0 2.1 2.8 2.8 2.8

2.8 2.8 2.1 0 2.8 2.8 2.8

2.8 2.8 2.1 2.1 0 2.8 2.8

2.8 2.8 2.1 2.1 2.8 0 2.8

2.8 2.8 2.1 2.1 2.8 2.8 0

2.8 2.8 2.1 2.1 2.8 2.8 2.8

При решении игровых задач методами линейного программирования необходимо представить данные условия в удобном для расчета виде:

Пусть игрок I принимает только оптимальную стратегию, а игрок II только чистые стратегии.

2.1×2+2.1×3+2.1×4+2.1×5+2.8×1+2.1×7 ≥v

2.1×1+2.8×3+2.8×4+2.8×5+2.8×6+2.8×7 ≥ v

2.1×1+2.1×2+2.1×4+2.1×5+2.1×6+2.1×7 ≥ v

2.1×1+2.1×2+2.1×3+2.1×5+2.1×6+2.1×7 ≥ v

2.8×1+2.8×2+2.8×3+2.8×4+2.8×6+2.8×7 ≥ v

2.8×1+2.8×2+2.8×3+2.8×4+2.8×5+2.8×7 ≥ v

2.8×1+2.8×2+2.8×3+2.8×4+2.8×5+2.8×6 ≥ v

Пусть

x_i/v=z_i

Тогда для первого игрока:

2.1z1+2.1z2+2.1z4+2.1z5+2.1z6+2.1z7 ≥ 1

2.1z1+2.1z2+2.1z3+2.1z5+2.1z6+2.1z7 ≥ 1

2.8z1+2.8z2+2.8z3+2.8z4+2.8z6+2.8z7 ≥ 1

2.8z1+2.8z2+2.8z3+2.8z4+2.8z5+2.8z7 ≥ 1

2.8z1+2.8z2+2.8z3+2.8z4+2.8z5+2.8z6 ≥ 1

Первый игрок стремиться сделать свой выигрыш максимальным (минимизировать проигрыш min 1/v).

Для второго игрока также можно составить неравенства, определяющие цену игры:

2.1z1+2.1z2+2.1z4+2.1z5+2.1z6+2.1z7≤v

2.1z1+2.1z2+2.1z3+2.1z5+2.1z6+2.1z7 ≤v

2.8z1+2.8z2+2.8z3+2.8z4+2.8z6+2.8z7 ≤v

2.8z1+2.8z2+2.8z3+2.8z4+2.8z5+2.8z7 ≤v

2.8z1+2.8z2+2.8z3+2.8z4+2.8z5+2.8z6 ≤v

В случае если совершить замену:

y_i/v=w_i

2.1w1+2.1w2+2.1w4+2.1w5+2.1w6+2.1w7≤1

2.1w1+2.1w2+2.1w3+2.1w5+2.1w6+2.1w7 ≤1

2.8w1+2.8w2+2.8w3+2.8w4+2.8w6+2.8w7 ≤1

2.8w1+2.8w2+2.8w3+2.8w4+2.8w5+2.8w7≤1

2.8w1+2.8w2+2.8w3+2.8w4+2.8w5+2.8w6 ≤1

Второй игрок стремиться сделать свой проигрыш минимальным (max 1/v).

Для решения поставленной задачи была использована среда Matlab 2010b. Библиотеки среды содержат функцию (linprog()) для решения задач линейного программирования. С помощью них можно определить оптимальные стратегии для первого и второго игрока.

Для заданной игры вектор w принимает значение:

w=[0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; ]Т

Для заданной игры вектор z принимает значение:

z=[0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; ]Т

Цена игры равна: v=[3.1429]

Исходя из равенства x=v*w, можно определить стратегии первого игрока:

x = [0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; ]Т

Исходя из равенства y=v*z, можно определить стратегии второго игрока:

y= [0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; ]Т

Матрица для игры при n=7 выглядит следующим образом:

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

2.8×2+2.8×3+2.8×4+2.8×5+2.8×6+2.8×7 ≥ 1

2.8×1+2.8×3+2.8×4+2.8×5+2.8×6+2.8×7 ≥ 1

2.1×1+2.1×2+2.1×4+2.1×5+2.1×6+2.1×7 ≥ 1

2.1×1+2.1×2+2.1×3+2.1×5+2.1×6+2.1×7 ≥ 1

2.8×1+2.8×2+2.8×3+2.8×4+2.8×6+2.8×7 ≥ 1

2.8×1+2.8×2+2.8×3+2.8×4+2.8×5+2.8×7 ≥ 1

2.8×1+2.8×2+2.8×3+2.8×4+2.8×5+2.8×6 ≥ 1

F(x) = x1+x2+x3+x4+x5+x6+x7 = min

найти максимум функции Ф(y) при ограничениях:

2.8y2+2.1y3+2.1y4+2.8y5+2.8y6+2.8y7 ≤ 1

2.8y1+2.1y3+2.1y4+2.8y5+2.8y6+2.8y7 ≤ 1

2.8y1+2.8y2+2.1y4+2.8y5+2.8y6+2.8y7 ≤ 1

2.8y1+2.8y2+2.1y3+2.8y5+2.8y6+2.8y7 ≤ 1

2.8y1+2.8y2+2.1y3+2.1y4+2.8y6+2.8y7 ≤ 1

2.8y1+2.8y2+2.1y3+2.1y4+2.8y5+2.8y7 ≤ 1

2.8y1+2.8y2+2.1y3+2.1y4+2.8y5+2.8y6 ≤ 1

Ф(y) = y1+y2+y3+y4+y5+y6+y7 = max

Решаем эти системы симплекс-методом.

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки B1 B2 B3 B4 B5 B6 B7 a = min(Ai)

A1 0 2.8 2.1 2.1 2.8 2.8 2.8 0

A2 2.8 0 2.1 2.1 2.8 2.8 2.8 0

A3 2.8 2.8 0 2.1 2.8 2.8 2.8 0

A4 2.8 2.8 2.1 0 2.8 2.8 2.8 0

A5 2.8 2.8 2.1 2.1 0 2.8 2.8 0

A6 2.8 2.8 2.1 2.1 2.8 0 2.8 0

A7 2.8 2.8 2.1 2.1 2.8 2.8 0 0

b = max(Bi) 2.8 2.8 2.1 2.1 2.8 2.8 2.8

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 0, которая указывает на максимальную чистую стратегию A1.

Верхняя цена игры b = min(bj) = 2.1.

Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 0 ≤ y ≤ 2.1. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.

Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

3. Находим решение игры в смешанных стратегиях.

Программная среда MATLAB представляет возможности по решению задач линейного программирования. С помощью функции linprog пользователь имеет возможность, задав параметры, получить решение задачи линейного программирования.

Функция linprog решает задачу линейного программирования в форме

f^T*x→inf,

A*x≤b, (1)

Aeq*x= beq,

lb≤x≤ub.

После выполнения программы были получены следующие результаты:

значение цены игры v=1.68;

оптимальная стратегия для МР-1: X=(0.2; 0.2; 0; 0; 0.2; 0.2; 0.2);

оптимальная стратегия для МР-2: Y=(0.2; 0.2; 0; 0; 0.2; 0.2; 0.2).

ЗАКЛЮЧЕНИЕ

Одним из основополагающих этапов синтеза модели управления мобильными интеллектуальными роботами является разработка аппарата принятия решений и планирование действий. Нередко данный вопрос осложнен ввиду наличия конфликтных ситуаций в среде функционирования. Методы теории игр позволяют описать создавшиеся ситуации и успешно прогнозировать результаты выбора возможных действий агента системы.

СПИСОК БИБЛИОГРАФИЧЕСКИХ ИСТОЧНИКОВ

Колобашкина Л.В., Основы теории игр. – М.: Изд-во Бином, 2011. – 162 с.

Дрешер М., Стратегические игры. Теория и приложения. – Советское радио, 1964. – 352 с.

Мак Кинси Дж., Введение в теорию игр. — М.: Физматлит, 1960. — 420 с.

Воробьев Н.Н., Теория игр. Лекции для экономистов-кибернетиков. – Л.: Издательство ЛГУ, 1974. – 160 с.

Вильямс Дж. Д., Современный стратег или букварь по теории стратегических игр. — Советское радио, 1960. – 266 с.

ПРИЛОЖЕНИЕ А

Листинг программы для решения задачи линейного программирования.